import bisect
from typing import List


class Solution:
    def maxEnvelopes(self, envelopes: List[List[int]]) -> int:
        envelopes = sorted(set((x, y) for x, y in envelopes), key=lambda x: (x[0], -x[1]))
        size = len(envelopes)

        dp = [float("inf")] * (size + 1)
        dp[0] = 0

        for x, y in envelopes:
            i = bisect.bisect_left(dp, y)
            dp[i] = y

        return bisect.bisect_right(dp, 20000) - 1


if __name__ == "__main__":
    print(Solution().maxEnvelopes(envelopes=[[5, 4], [6, 4], [6, 7], [2, 3]]))  # 3
    print(Solution().maxEnvelopes(envelopes=[[1, 1], [1, 1], [1, 1]]))  # 1

    # 测试用例16 : 3
    print(Solution().maxEnvelopes([[1, 3], [3, 5], [6, 7], [6, 8], [8, 4], [9, 5]]))

    # 测试用例53 : 9
    print(Solution().maxEnvelopes(
        [[2, 1], [4, 1], [6, 2], [8, 3], [10, 5], [12, 8], [14, 13], [16, 21], [18, 34], [20, 55]]))
